<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  
  <title>数据结构与算法：时间复杂度 | Rogerspy&#39;s Home</title>
  
  <meta name="keywords" content="Machine Learning, Deep Learning, NLP">
  
  

  
  <link rel="alternate" href="/atom.xml" title="Rogerspy's Home">
  

  <meta name="HandheldFriendly" content="True">
  <meta name="apple-mobile-web-app-capable" content="yes">
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <!-- meta -->
  
  
  <meta name="theme-color" content="#FFFFFF">
  <meta name="msapplication-TileColor" content="#1BC3FB">
  <meta name="msapplication-config" content="https://cdn.jsdelivr.net/gh/xaoxuu/assets@master/favicon/favicons/browserconfig.xml">
  

  <!-- link -->
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.css">
  
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/node-waves@0.7.6/dist/waves.min.css">
  
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.10.1/css/all.min.css">
  
  
  <link rel="shortcut icon" type="image/x-icon" href="https://cdn.jsdelivr.net/gh/xaoxuu/assets@master/favicon/favicon.ico">
  <link rel="icon" type="image/x-icon" sizes="32x32" href="https://cdn.jsdelivr.net/gh/xaoxuu/assets@master/favicon/favicons/favicon-32x32.png">
  <link rel="apple-touch-icon" type="image/png" sizes="180x180" href="https://cdn.jsdelivr.net/gh/xaoxuu/assets@master/favicon/favicons/apple-touch-icon.png">
  <link rel="mask-icon" color="#1BC3FB" href="https://cdn.jsdelivr.net/gh/xaoxuu/assets@master/favicon/favicons/safari-pinned-tab.svg">
  <link rel="manifest" href="https://cdn.jsdelivr.net/gh/xaoxuu/assets@master/favicon/favicons/site.webmanifest">
  

  

  
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/xaoxuu/cdn-material-x@19.5/css/style.css">
  

  <script>
    function setLoadingBarProgress(num) {
      document.getElementById('loading-bar').style.width=num+"%";
    }
  </script>
  

  
  
  <!-- 时间线 -->
  <link rel="stylesheet" href="/css/timeline.css">
  <!-- 血小板-->
  <link rel="stylesheet" href="/live2d/css/live2d.css">
  <style>
	.article p .mjx-math {
	    font-family: Menlo,Monaco,courier,monospace,"Lucida Console",'Source Code Pro',"Microsoft YaHei",Helvetica,Arial,sans-serif,Ubuntu;
        background: none;
        padding: 2px;
        border-radius: 4px;
	}
  </style>
</head>

<body>
  
  
  <header class="l_header pure">
  <div id="loading-bar-wrapper">
    <div id="loading-bar" class="pure"></div>
  </div>

	<div class='wrapper'>
		<div class="nav-main container container--flex">
      <a class="logo flat-box" href='/' >
        
          Rogerspy's Home
        
      </a>
			<div class='menu navgation'>
				<ul class='h-list'>
          
  					
  						<li>
								<a class="nav flat-box" href="/blog/"
                  
                  
                  id="blog">
									<i class='fas fa-edit fa-fw'></i>&nbsp;博客
								</a>
							</li>
      			
  						<li>
								<a class="nav flat-box" href="/video/"
                  
                  
                  id="video">
									<i class='fas fa-film fa-fw'></i>&nbsp;视频小站
								</a>
							</li>
      			
  						<li>
								<a class="nav flat-box" href="/material/"
                  
                  
                  id="material">
									<i class='fas fa-briefcase fa-fw'></i>&nbsp;学习资料
								</a>
							</li>
      			
  						<li>
								<a class="nav flat-box" href="/diary/"
                  
                  
                  id="diary">
									<i class='fas fa-book fa-fw'></i>&nbsp;随心记
								</a>
							</li>
      			
  						<li>
								<a class="nav flat-box" href="/categories/"
                  
                    rel="nofollow"
                  
                  
                  id="categories">
									<i class='fas fa-folder-open fa-fw'></i>&nbsp;分类
								</a>
							</li>
      			
  						<li>
								<a class="nav flat-box" href="/tags/"
                  
                    rel="nofollow"
                  
                  
                  id="tags">
									<i class='fas fa-hashtag fa-fw'></i>&nbsp;标签
								</a>
							</li>
      			
  						<li>
								<a class="nav flat-box" href="/blog/archives/"
                  
                    rel="nofollow"
                  
                  
                  id="blogarchives">
									<i class='fas fa-archive fa-fw'></i>&nbsp;归档
								</a>
							</li>
      			
      		
				</ul>
			</div>

			
				<div class="m_search">
					<form name="searchform" class="form u-search-form">
						<input type="text" class="input u-search-input" placeholder="搜索" />
						<i class="icon fas fa-search fa-fw"></i>
					</form>
				</div>
			
			<ul class='switcher h-list'>
				
					<li class='s-search'><a class="fas fa-search fa-fw" href='javascript:void(0)'></a></li>
				
				<li class='s-menu'><a class="fas fa-bars fa-fw" href='javascript:void(0)'></a></li>
			</ul>
		</div>

		<div class='nav-sub container container--flex'>
			<a class="logo flat-box"></a>
			<ul class='switcher h-list'>
				<li class='s-comment'><a class="flat-btn fas fa-comments fa-fw" href='javascript:void(0)'></a></li>
        
          <li class='s-toc'><a class="flat-btn fas fa-list fa-fw" href='javascript:void(0)'></a></li>
        
			</ul>
		</div>
	</div>
</header>
	<aside class="menu-phone">
    <header>
		<nav class="menu navgation">
      <ul>
        
          
            <li>
							<a class="nav flat-box" href="/"
                
                
                id="home">
								<i class='fas fa-clock fa-fw'></i>&nbsp;近期文章
							</a>
            </li>
          
            <li>
							<a class="nav flat-box" href="/blog/archives/"
                
                  rel="nofollow"
                
                
                id="blogarchives">
								<i class='fas fa-archive fa-fw'></i>&nbsp;文章归档
							</a>
            </li>
          
            <li>
							<a class="nav flat-box" href="/blog/"
                
                
                id="blog">
								<i class='fas fa-edit fa-fw'></i>&nbsp;我的博客
							</a>
            </li>
          
            <li>
							<a class="nav flat-box" href="/video/"
                
                  rel="nofollow"
                
                
                id="video">
								<i class='fas fa-film fa-fw'></i>&nbsp;我的视频
							</a>
            </li>
          
            <li>
							<a class="nav flat-box" href="/material/"
                
                  rel="nofollow"
                
                
                id="material">
								<i class='fas fa-briefcase fa-fw'></i>&nbsp;学习资料
							</a>
            </li>
          
            <li>
							<a class="nav flat-box" href="/about/"
                
                  rel="nofollow"
                
                
                id="about">
								<i class='fas fa-info-circle fa-fw'></i>&nbsp;关于小站
							</a>
            </li>
          
       
      </ul>
		</nav>
    </header>
	</aside>
<script>setLoadingBarProgress(40);</script>



  <div class="l_body nocover">
    <div class='body-wrapper'>
      <div class='l_main'>
  

  
    <article id="post" class="post white-box article-type-post" itemscope itemprop="blogPost">
      


  <section class='meta'>
    
    
    <div class="meta" id="header-meta">
      
        
  
    <h1 class="title">
      <a href="/2021/04/22/ds-time-complexity/">
        数据结构与算法：时间复杂度
      </a>
    </h1>
  


      
      <div class='new-meta-box'>
        
          
        
          
            
  <div class='new-meta-item author'>
    <a href="https://rogerspy.gitee.io" rel="nofollow">
      
        <i class="fas fa-user" aria-hidden="true"></i>
      
      <p>Rogerspy</p>
    </a>
  </div>


          
        
          
            <div class="new-meta-item date">
  <a class='notlink'>
    <i class="fas fa-calendar-alt" aria-hidden="true"></i>
    <p>2021-04-22</p>
  </a>
</div>

          
        
          
            
  
  <div class='new-meta-item category'>
    <a href='/categories/数据结构与算法/' rel="nofollow">
      <i class="fas fa-folder-open" aria-hidden="true"></i>
      <p>数据结构与算法</p>
    </a>
  </div>


          
        
          
            
  
    <div class="new-meta-item browse busuanzi">
      <a class='notlink'>
        <i class="fas fa-eye" aria-hidden="true"></i>
        <p>
          <span id="busuanzi_value_page_pv">
            <i class="fas fa-spinner fa-spin fa-fw" aria-hidden="true"></i>
          </span>
        </p>
      </a>
    </div>
  


          
        
          
            

          
        
          
            
  
    <div style="margin-right: 10px;">
      <span class="post-time">
        <span class="post-meta-item-icon">
          <i class="fa fa-keyboard"></i>
          <span class="post-meta-item-text">  字数统计: </span>
          <span class="post-count">4.5k字</span>
        </span>
      </span>
      &nbsp; | &nbsp;
      <span class="post-time">
        <span class="post-meta-item-icon">
          <i class="fa fa-hourglass-half"></i>
          <span class="post-meta-item-text">  阅读时长≈</span>
          <span class="post-count">19分</span>
        </span>
      </span>
    </div>
  

          
        
      </div>
      
        <hr>
      
    </div>
  </section>


      <section class="article typo">
        <div class="article-entry" itemprop="articleBody">
          <p><img src="https://cdn.jsdelivr.net/gh/rogerspy/blog-imgs/20210820161802.png" alt></p>
<p>就像做菜有好吃和不好吃一样，算法也有好的算法和不好的算法。那么我们怎么评价一个算法的好坏呢？</p>
<h1 id="1-时间复杂度"><a href="#1-时间复杂度" class="headerlink" title="1. 时间复杂度"></a>1. 时间复杂度</h1><p>时间复杂度是用来估算算法需要执行的时间的。但是我们并不是直接用时间来估计，而是用一个<strong>函数</strong>。</p>
<blockquote>
<p>时间复杂度不是算法需要执行多久，而是算法需要执行多少步。</p>
</blockquote>
<a id="more"></a>
<p>这种评估方法看起来很奇怪，为什么不直接用时间来评估呢？很显然，一个需要 10 秒的的算法肯定是不如只需要 1 秒的算法啊。事实并非如此，比如同一个排序算法，对 100 个元素进行排序和对 1000 个元素进行排序所用时间肯定是不同的，能说算法变坏了吗？算法运算的时间依赖于输入参数的大小。</p>
<p>如果一个排序算法的输入本来就已经排好了序，那么它的运算时间肯定要比乱序输入更快。即使输入参数大小相同，算法的运算时间也会有差异。</p>
<p>另外，CPU 运算波动，磁盘读写效率等等都会影响算法的运算时间。</p>
<p>所以，即使是同一个算法，它的运算时间也会有：</p>
<ul>
<li>最长运算时间</li>
<li>最短运算时间</li>
<li>平均运算时间</li>
</ul>
<p>而我们通常关心的是一个算法的最长运算时间（抱最好的希望，做最坏的打算）。所以我们对算法性能的分析要包含两方面的考虑：</p>
<ol>
<li>忽略掉依赖于机器的因素；</li>
<li>关注运行时间的增长，而不是去检查真正的运行时间.</li>
</ol>
<h2 id="1-1-计算时间复杂度"><a href="#1-1-计算时间复杂度" class="headerlink" title="1.1 计算时间复杂度"></a>1.1 计算时间复杂度</h2><p>举个例子：找到一个数组中的最小数字。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">第一步：开始</span><br><span class="line">第二步：声明变量 min</span><br><span class="line">第三步：从输入数组中循环取值</span><br><span class="line">      3.1 对比从数组中取到的值 n 和 min 的大小</span><br><span class="line">      3.2 如果 n &lt; min</span><br><span class="line">      3.3 令 min = n</span><br><span class="line">第四步：返回 min 的值</span><br></pre></td></tr></table></figure>
<p>假设 cpu 的运算是平稳没有波动的，每一步所需的时间相同。我们来看下上面的过程：</p>
<ul>
<li>第一步：1 个操作；</li>
<li>第二步：1 个操作</li>
<li>第三步：这一步需要执行 $m$ （数组中有 $m$ 个元素）次，假设每一小步是 1 个操作，每一次循环就需要 4 个操作，那么这个循环就相当于需要 $4m$ 个操作</li>
<li>第四步： 1 个操作</li>
</ul>
<p>总共需要 $4m+3$ 个操作。但是这个表达式太过于具体了，不能对比不同的算法。我们需要进一步简化时间复杂度的计算。</p>
<h2 id="1-2-渐进分析"><a href="#1-2-渐进分析" class="headerlink" title="1.2 渐进分析"></a>1.2 渐进分析</h2><h3 id="1-2-1-符号表示"><a href="#1-2-1-符号表示" class="headerlink" title="1.2.1 符号表示"></a>1.2.1 符号表示</h3><p>为了更方便表示时间复杂度，我们使用渐进符号来表示。主要有三种符号：</p>
<ul>
<li><p>$O$ 符号：表示算法运算的上限，即表现最差的运算时间。</p>
<p><img width="300" src="https://cdn.jsdelivr.net/gh/rogerspy/blog-imgs/big0.png"></p>
<script type="math/tex; mode=display">
O(g(n)) = \{f(n) ~|~  \exists c>0, ~ n \ge n_0,~ 0\le f(n)\le cg(n) \}</script><p>$O(g(n))$ 是函数 $f(n)$ 的集合。$f(n)$ 满足以下条件：存在一个正实数 $c$，使得当 $n$ 足够大时（大于一个阈值 $n_0$） ，所有的 $f(n)$ 都小于 $cg(n)$。</p>
</li>
<li><p>$\Omega$ 符号：表示算法运算下限，即表现最好的运算时间。</p>
<p><img width="300" src="https://cdn.jsdelivr.net/gh/rogerspy/blog-imgs/omega.png"></p>
<script type="math/tex; mode=display">
\Omega(g(n)) = \{f(n)~ \vert ~ \exists c>0,~ n\ge n_0,~ 0 \le f(n) \le cg(n) \}</script><p>$\Omega(g(n))$ 是函数  $f(n)$ 的集合。$f(n)$ 满足以下条件：存在一个正实数 $c$，使得当 $n$ 足够大时（大于一个阈值 $n_0$），所有的 $f(n)$ 都大于 $cg(n)$。</p>
</li>
<li><p>$\Theta$ 符号：表示算法运算时间的平均水平，即平均运算时间。</p>
<p><img width="300" src="https://cdn.jsdelivr.net/gh/rogerspy/blog-imgs/theta.png"></p>
<script type="math/tex; mode=display">
\Theta(g(n)) = \{f(n)~ \vert ~ \exists c_1,c_2>0,~ n \gt n_0,~ 0 \le c_1g(n) \le f(n) \le c_2g(n)\}</script><p>$\Theta(g(n))$ 是函数 $f(n)$ 的集合。$f(n)$ 满足以下条件：存在正实数 $c_1,c_2$，使得当 $n$ 足够大时（大于一个阈值 $n_0$），所有的 $f(n)$ 都介于 $c_1g(n)$ 和 $c_2g(n)$ 之间。</p>
</li>
</ul>
<h3 id="1-2-2-渐进分析"><a href="#1-2-2-渐进分析" class="headerlink" title="1.2.2 渐进分析"></a>1.2.2 渐进分析</h3><p>渐进分析遵循三个原则：</p>
<ul>
<li>分析最坏的情况，即 $O(g(n))$。</li>
<li>不关心系数和低阶项。从上面我们对 $O(g(n))$ 的定义可以看出，系数相当于 $c$，而我们关心的是 $g(n)$。如前所说，对时间复杂度的分析更关注的是运行时间的增长。当 $n$ 足够大的时候，低阶项对运行时间的增长影响力越来越低，所以也不是我们关心的点。</li>
<li>分析当 $n$  足够大的时候的运行时间。</li>
</ul>
<p>渐进分析是将时间复杂度函数做无穷近似。比如上面的例子中 $4m+3$ 可以泛化成 $km+c$。忽略掉系数 $k$ 和低阶项 $c$，所以上面的算法时间复杂度为 $O(m)$。</p>
<p>$O$ 表示方程的阶（<em>order</em>）。常见的时间复杂度及其对比：</p>
<div class="table-container">
<table>
<thead>
<tr>
<th>$n$</th>
<th>$O(1)$</th>
<th>$O(\log n)$</th>
<th>$O(n)$</th>
<th>$O(n \log n)$</th>
<th>$O(n^2)$</th>
<th>$O(2^n)$</th>
</tr>
</thead>
<tbody>
<tr>
<td>1</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
</tr>
<tr>
<td>10</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
</tr>
<tr>
<td>100</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
<td>40170 trillion years</td>
</tr>
<tr>
<td>1,000</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
<td>&gt; vigintillion years</td>
</tr>
<tr>
<td>10,000</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
<td>2 min</td>
<td>&gt; centillion years</td>
</tr>
<tr>
<td>100,000</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
<td>1 sec</td>
<td>3 hours</td>
<td>&gt; centillion years</td>
</tr>
<tr>
<td>1,000,000</td>
<td>&lt; 1 sec</td>
<td>&lt; 1 sec</td>
<td>1 sec</td>
<td>20 sec</td>
<td>12 days</td>
<td>&gt; centillion years</td>
</tr>
</tbody>
</table>
</div>
<h2 id="1-3-非递归算法"><a href="#1-3-非递归算法" class="headerlink" title="1.3 非递归算法"></a>1.3 非递归算法</h2><p>非递归算法时间复杂度计算步骤如下：</p>
<ol>
<li>找到问题的输入数据规模，比如 2.1 节中的 $m$；</li>
<li>找出算法的基本操作，比如 2.1 节中的循环操作；</li>
<li>建立算法中涉及到的操作数求和表达式；</li>
<li>利用 $O$ 准则进行简化。</li>
</ol>
<p>具体例子可以看 2.1 节的例子。</p>
<h2 id="1-4-递归算法"><a href="#1-4-递归算法" class="headerlink" title="1.4 递归算法"></a>1.4 递归算法</h2><p>递归算法的时间复杂度有两种方法进行计算：</p>
<ul>
<li>迭代法：每次运算只是将数据规模减一，比如斐波那契数列；</li>
<li>主定理：利用分治的思想，将问题拆解成几份，分别求解。</li>
</ul>
<h3 id="1-4-1-迭代法"><a href="#1-4-1-迭代法" class="headerlink" title="1.4.1 迭代法"></a>1.4.1 迭代法</h3><p>以斐波那契数列为例：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">第一步：定义函数 fab(n)</span><br><span class="line">第二步：判断 n 是否为 0</span><br><span class="line">第三步：如果 n == 0，返回 1</span><br><span class="line">第四步：如果 n != 0, 返回 fab(n-1) * n</span><br></pre></td></tr></table></figure>
<p>假设 <code>fab(n)</code> 需要执行 $C(n)$ 次，$C(n)$ 的计算公式为：</p>
<script type="math/tex; mode=display">
C(n) = C(n-1)+1</script><p>$C(n-1)$ 为 <code>fab(n-1)</code> 的运算次数，当 $n=0$ 时，<code>fab(0)</code> 直接返回值，所以只需要运算 1 次，即 $C(0)=1$。</p>
<script type="math/tex; mode=display">
\begin{equation} \nonumber
\begin{aligned}
C(n) &= C(n-1)+1\\\\
     &= [C(n-2)+1]+1\\\\
     &= [C(n-3)+1]+2\\\\
     & \dots \\\\
     &= C(n-i)+i \\\\
     & \dots \\\\
     &= C(n-n)+n \\\\
     &= n
\end{aligned}
\end{equation}</script><p>所以这个算法的时间复杂度为 $O(n)$。</p>
<h3 id="1-4-2-主定理"><a href="#1-4-2-主定理" class="headerlink" title="1.4.2 主定理"></a>1.4.2 主定理</h3><p>当我们使用分治思想求解递归问题的时候，就可以用“主定理”（<em>master theorem</em>）的方法来计算时间复杂度。具体来说，当递归函数的时间复杂度计算公式满足：</p>
<blockquote>
<script type="math/tex; mode=display">
T(n)=aT(\frac{n}{b})+f(n)</script><p>其中：</p>
<ul>
<li>$n$：输入数据规模</li>
<li>$a$：将递归问题分解成子问题的个数</li>
<li>$n/b$：每个子问题的规模，</li>
<li>$f(n)$：递归操作之外所需要的操作次数，包括问题分解和结果合并</li>
</ul>
<p>$a$ 和 $b$ 是大于 $0$ 的常数，$f(n)$ 是渐进函数，即当 $n \to \infty$ 时 $f(n)&gt;0$。</p>
</blockquote>
<p>上面的公式可以理解为：对于一个规模为 $n$ 的问题，我们把它分解成 $a$ 个子问题，每个子问题规模为 $n/b$ 指的是 $\lfloor{n/b}\rfloor$ 或者 $\lceil{n/b}\rceil$（$\lfloor \cdot \rfloor$ 表示是向下取整，$\lceil \cdot\rceil$ 表示向上取整），然后将问题的解通过 $f(n)$次操作整合到一起。</p>
<p><img width="600" src="https://cdn.jsdelivr.net/gh/rogerspy/blog-imgs/20210822131342.png"></p>
<p>首先构建一棵递归任务分解树，观察每一层的变化：</p>
<blockquote>
<p>第一层：</p>
<ul>
<li>子问题的数目：$a^0$</li>
<li><p>每个子问题的规模：$\frac{n}{b^0}$</p>
</li>
<li><p>合并子问题需要花费的操作次数：$f(n)$</p>
</li>
</ul>
<p>第二层：</p>
<ul>
<li>子问题的数目：$a^1$</li>
<li>每个子问题的规模：$\frac{n}{b^1}$</li>
<li>合并子问题需要花费的操作次数：$af(n/b)$</li>
</ul>
<p>第三层：</p>
<ul>
<li>子问题的数目：$a^2$</li>
<li>每个子问题的规模：$\frac{n}{b^2}$</li>
<li>合并子问题需要花费的操作次数：$a^2f(n/b^2)$</li>
</ul>
<p>…</p>
<p>最后一层：</p>
<ul>
<li>子问题的数目：$a^2$</li>
<li>每个子问题的规模：$\frac{n}{b^h}$</li>
<li>合并子问题需要花费的操作次数：$a^hf(n/b^h)$</li>
</ul>
</blockquote>
<div class="container" style="margin-top:40px;margin-bottom:20px;">
    <div style="background-color:#54c7ec;height:36px;line-height:36px;vertical-align:middle;">
        <div style="margin-left:10px">
            <font color="white" size="4">
                • NOTE
            </font>
        </div>
    </div>
    <div style="background-color:#F3F4F7">
        <div style="padding:15px 10px 15px 20px;line-height:1.5;">
            第一层，“合并子问题需要花费的操作次数”，实际上指的是要解决一个和原问题等规模的问题所需要的操作次数。因为第一层还没有对问题进行分解，也就谈不上合并子问题，上面的说法只是为了和下面保持一致。
        </div>    
    </div>    
</div>

<ul>
<li><p>树的高度 $h$</p>
<p>对于分治递归方法，最后一层的每个子问题规模为 1，即 $\frac{n}{b^h}=1$，由此可得 </p>
<script type="math/tex; mode=display">
h = \log_b n</script></li>
<li><p>叶子结点个数</p>
<p>叶子结点的个数即为最后一层子问题的数目 $a^h$。由上一步 $h = \log_b n$ 可得，叶子结点的个数为 $a^{\log_b n}$。根据换底公式 $x^{\log_ny}=y^{\log_nx}$ 可以将上式改写成  $n^{\log_ba}$。注意每个子问题的划分都是 $n/b$ 的均匀划分，所以时间复杂度也应该用 $\Theta$ 表示，即</p>
<script type="math/tex; mode=display">
\Theta(n^{\log_ba})</script></li>
<li><p>合并子问题需要花费的操作次数总和</p>
<p>根据我们对每层递归树的分析可以发现，每层合并子问题需要的操作次数为 $a^if\Big(\frac{n}{b^i}\Big)$，只需要将每层次数相加即可得到总次数：</p>
<script type="math/tex; mode=display">
\sum_{i=0}^{\log_bn-1}a^if\Big(\frac{n}{b^i}\Big)</script></li>
</ul>
<p>有了递归操作总次数和分解合并操作总次数以后，根据递归函数时间复杂度公式可得</p>
<script type="math/tex; mode=display">
\begin{equation} \nonumber
\begin{aligned}
T(n) &= aT(\frac{n}{b})+f(n) \\\\
     &= \Theta(n^{\log_ba})+\sum_{i=0}^{\log_bn-1}a^if\Big(\frac{n}{b^i}\Big) \\\\
     &= \Theta(n^{\log_ba})+g(n)
\end{aligned}
\end{equation}</script><p>从中我们可以看出，整个递归的时间复杂度取决于 $f(n)$，分三种情况讨论：</p>
<ol>
<li><p>如果右边第一项的阶数比第二项高， $T(n)$ 主要由第一项决定，这意味着递归树的时间主要消耗在子问题的递归上。根据时间复杂度分析“忽略低阶项”的原则：</p>
<script type="math/tex; mode=display">
T(n) = \Theta(n^{\log_ba})</script></li>
<li><p>如果右边第二项的阶数比第一项高， $T(n)$ 主要由第二项决定，这意味着递归树的时间主要消耗在对问题的分解和解的合并上，根据时间复杂度分析“忽略低阶项”的原则：</p>
<script type="math/tex; mode=display">
T(n) = \Theta(f(n))</script></li>
<li><p>如果两部分的阶数相等，意味着递归树的总时间分布是均匀的，由两部分共同决定：</p>
<script type="math/tex; mode=display">
T(n)=\Theta(n^{\log_b a} \cdot \log n)</script></li>
</ol>
<h3 id="1-4-3-主定理证明"><a href="#1-4-3-主定理证明" class="headerlink" title="1.4.3 主定理证明"></a>1.4.3 主定理证明</h3><p>为了方便写证明过程，将以上三种情况用数学语言进行描述：</p>
<ol>
<li><p>$\exists \epsilon&gt;0\ s.t.\ f(n)=O(n^{\log_ba-\epsilon})$，则 $T(n)=\Theta(n^{\log_ba})$。</p>
<p>证明：</p>
<script type="math/tex; mode=display">
\begin{equation} \nonumber
\begin{aligned}
f(n) &= O(n^{(\log_ba)-\epsilon}) \\\\
\Rightarrow f(\frac{n}{b^i}) &= O((\frac{n}{b^i})^{(\log_ba)-\epsilon}) \\\\
                 &\le c(\frac{n}{b^i})^{(\log_ba)-\epsilon} \\\\
\Rightarrow a^if(\frac{n}{b^i}) &\le c a^i(\frac{n}{b^i})^{(\log_ba)-\epsilon} \\\\
                    &= cn^{(\log_ba)-\epsilon} \cdot (\frac{a}{b^{(\log_ba)-\epsilon}})^i\\\\
                    &= cn^{(\log_ba)-\epsilon} \cdot (\frac{a}{a^{(\log_bb)}\cdot b^ {-\epsilon}})^i\\\\
                    &= cn^{(\log_ba)-\epsilon} \cdot (b^\epsilon)^i \\\\
\Rightarrow \sum_{i=0}^{\log_bn-1}a^if\Big(\frac{n}{b^i}\Big) &\le \sum_{i=0}^{\log_bn-1} cn^{(\log_ba)-\epsilon} \cdot (b^\epsilon)^i \\\\ 
                    &= cn^{(\log_ba)-\epsilon} \cdot \sum_{i=0}^{\log_bn-1}(b^\epsilon)^i\\\\
                    &= cn^{(\log_ba)-\varepsilon} \cdot \frac{(b^\varepsilon)^{\log_bn}-1}{b^\varepsilon-1} \\\\
                    &= cn^{(\log_ba)-\varepsilon} \cdot \frac{n^\epsilon-1}{b^\epsilon-1} \\\\
                    &= \frac{c}{b^\epsilon-1} \left[ n^{\log_ba}-n^{(\log_ba)-\epsilon} \right] \\\\
                    &= O(n^{\log_ba})
\end{aligned}
\end{equation}</script><p>由此可得</p>
<script type="math/tex; mode=display">
T(n) =\Theta(n^{\log_ba}) +O(n^{\log_ba})</script><p>由于上式右侧两部分的函数增长率相同，所以</p>
<script type="math/tex; mode=display">
T(n) = \Theta(n^{\log_ba})</script><blockquote>
<p>个人理解是，$\Theta$ 表示的是平均水平，即它可能有更高的上限和更低的下限。而 $O$ 已经是上限了，当 $\Theta$ 取上限的时候，阶数是要比 $O$ 更高的。所以，当 $\Theta$ 和 $O$ 的增长率是相同的时候，复杂度取 $\Theta$。</p>
</blockquote>
</li>
<li><p>$\exists \epsilon&gt;0\ s.t.\ f(n)=\Omega(n^{\log_ba+\epsilon})$，且 $\exists c&lt;1$。当 $n \to \infty$， $a\, f(\frac{n}{b})\le c\, f(n)$。此时 $T(n)=\Theta(f(n))$。</p>
<p>证明：</p>
</li>
</ol>
<script type="math/tex; mode=display">
\begin{equation} \nonumber
\begin{aligned}
af(\frac{n}{b}) &\le cf(n) \\\\
\Rightarrow f\Big(\frac{n}{b}\Big) &\le \frac{c}{a}f(n)\\\\
\Rightarrow f\Big(\frac{n}{b^2}\Big) &\le \frac{c}{a}f\Big(\frac nb\Big)\le\Big(\frac{c}{a}\Big)^2f(n)\\\\
&\vdots\\\\
f\Big(\frac{n}{b^i}\Big) &\le\Big(\frac{c}{a}\Big)^if(n)\\\\
\Rightarrow a^i\, f\Big(\frac{n}{b^i}\Big) &\le c^i\, f(n)\\\\
\Rightarrow g(n) &\le f(n)\sum_{i=1}^{\log_bn-1}\\\\
     &\le f(n)\sum_{i=1}^\infty c^i\\\\
     &= \frac{1}{1-c}f(n)\\\\
\Rightarrow g(n) &= O(f(n))\\\\
g(n) &= f(n) + af(\frac{n}{b})+ \dots + a^{\log_bn-1}f(\frac{n}{b^{\log_bn-1}}) \\\\
     &\ge f(n)\\\\
\Rightarrow g(n) &= \Omega(f(n))
\end{aligned}
\end{equation}</script><p>由 $g(n)=O(f(n))$ 和 $g(n)=\Omega(f(n))$ 可得：</p>
<script type="math/tex; mode=display">
g(n) = \Theta(f(n))=\Theta(n^{\log_ba+\epsilon})</script><p>此时</p>
<script type="math/tex; mode=display">
T(n) = \Theta(n^{\log_ba})+\Theta(n^{\log_ba+\epsilon})</script><p>后者的阶数更高，所以</p>
<script type="math/tex; mode=display">
T(n) = \Theta(f(n))</script><ol>
<li>如果 $f(n)=\Theta(n^{\log_ba})$，则 $T(n)=\Theta(n{\log_ba}\cdot\log n)$。</li>
</ol>
<p>证明：</p>
<script type="math/tex; mode=display">
\begin{equation} \nonumber
\begin{aligned}
f(n) &= \Theta(n^{\log_ba}) \\\\
\Rightarrow f(\frac{n}{b^i}) &= \Theta((\frac{n}{b^i})^{\log_ba}) \\\\
\Rightarrow c_1(\frac{n}{b^i})^{\log_ba} &\le f(\frac{n}{b^i}) \le c_2(\frac{n}{b^i})^{\log_ba}\\\\
\Rightarrow a^i \cdot c_1(\frac{n}{b^i})^{\log_ba} &\le a^i \cdot f(\frac{n}{b^i}) \le a^i\cdot c_2(\frac{n}{b^i})^{\log_ba}\\\\
\Rightarrow c_1n^{\log_ba}(\frac{a}{b^{\log_ba}})^i &\le a^if(\frac{n}{b^i})\le c_2n^{\log_ba}(\frac{a}{b^{\log_ba}})^i\\\\
c_1n^{\log_ba}(1)^i &\le a^if(\frac{n}{b^i})\le c_2n^{\log_ba}(1)^i\\\\
\sum_{i=0}^{\log_bn-1} c_1n^{\log_ba}(1)^i &\le \sum_{i=0}^{\log_bn-1}a^if(\frac{n}{b^i})\le \sum_{i=0}^{\log_bn-1} c_2n^{\log_ba}(1)^i\\\\
c_1n^{\log_ba}\cdot \log_bn &\le g(n) \le c_2n^{\log_ba} \\\\
c_1n^{\log_ba}\frac{\log n}{\log b} &\le g(n) \le c_2 n^{\log_ba} \frac{\log n}{\log b}\\\\
\frac{c_1}{\log b} \cdot n^{\log_ba}\cdot \log n &\le g(n) \le \frac{c_2}{\log b} n^{\log_ba} \cdot \log n \\\\
\Rightarrow g(n) &= \Theta(n^{\log_ba}\cdot \log n) \\\\
\Rightarrow T(n) &= \Theta(n^{\log_ba}) +\Theta(n^{\log_ba}\cdot \log b)
\end{aligned}
\end{equation}</script><p>由于 $\Theta(n^{\log_ba}\cdot \log n)$  是高阶项，所以</p>
<script type="math/tex; mode=display">
T(n) = \Theta(n^{\log_ba}\cdot \log n)</script><h3 id="1-4-4-主定律应用"><a href="#1-4-4-主定律应用" class="headerlink" title="1.4.4 主定律应用"></a>1.4.4 主定律应用</h3><script type="math/tex; mode=display">
T(n)=aT(\frac{n}{b})+f(n) = \begin{cases}
\Theta(n^{\log_ba}), & \text{if}\quad f(n)=O(n^{\log_ba-\epsilon}) \\\\
\Theta(n^{\log_ba}\cdot \log n), &\text{if}\quad f(n)=\Theta(n^{\log_ba})\\\\
\Theta(f(n)) , & \text{if} \quad f(n) = \Omega(n^{\log_ba+\epsilon})
\end{cases}</script><blockquote>
<p>$T(n)=3T(n/2)+n^2$</p>
<ol>
<li>$a=3, b=2$，$f(n)=n^2$</li>
<li><p>$\log_ba=\log_23 \approx 1.58 &lt; 2$</p>
</li>
<li><p>即 $f(n)&lt;n^{\log_23+\epsilon}$</p>
</li>
<li>$T(n)=\Theta (f(n))=\Theta(n^2)$</li>
</ol>
</blockquote>
<h3 id="1-4-5-主定律的局限性"><a href="#1-4-5-主定律的局限性" class="headerlink" title="1.4.5 主定律的局限性"></a>1.4.5 主定律的局限性</h3><p>主定律在以下情况下不可用：</p>
<ul>
<li>$T(n)$ 是非单调函数，比如 $T(n)=\sin(n)$;</li>
<li>$ f(n)$ 是非多项式，比如 $f(n)=2^n$;</li>
<li>$a$ 不是常数，比如 $a=2n$；</li>
<li>$a&lt;1$。</li>
</ul>
<h2 id="1-5-关于时间复杂度的讨论"><a href="#1-5-关于时间复杂度的讨论" class="headerlink" title="1.5 关于时间复杂度的讨论"></a>1.5 关于时间复杂度的讨论</h2><h3 id="1-5-1-渐进分析有什么缺点？"><a href="#1-5-1-渐进分析有什么缺点？" class="headerlink" title="1.5.1 渐进分析有什么缺点？"></a>1.5.1 渐进分析有什么缺点？</h3><ul>
<li>由于 渐近分析是假设 $n\to \infty$ 时才成立的，通常情况下 ，算法需要解决的问题规模不会这么大。此时，估算结果会与实际情况有所偏差。</li>
<li>由于渐近分析考虑的是时间增长率，忽略掉了低阶项和系数。所以无法区分增长率相同而系数不同的情况。比如 $f(n)=100n$ 和 $g(n)=n\log_2n$ ，按照渐近分析，$f(n)$ 的复杂度要优于 $g(n)$。然而只有当问题规模达到宇宙原子总数量级的时候，这种情况才成立。而我们实际应用中问题规模通常是远小于这个量级。</li>
</ul>
<h3 id="1-5-2-为什么通常关心的是-O-f-n-？"><a href="#1-5-2-为什么通常关心的是-O-f-n-？" class="headerlink" title="1.5.2 为什么通常关心的是 $O(f(n))$？"></a>1.5.2 为什么通常关心的是 $O(f(n))$？</h3><p>首先， $\Omega(f(n))$ 对各种条件要求比较苛刻，所以我们主要讨论 $\Theta(f(n))$ 和 $O(f(n))$。</p>
<ul>
<li><p>当我们讨论 “平均” 情况的时候，意味着要对输入数据的分布作出假设。在做这种假设的时候需要大量的数据支持。这就意味着分析结果是不普适的，因为不同的数据有不同的分布。所以通常情况下，“平均” 分析结果并不准确。</p>
</li>
<li><p>“最坏” 的情况得到的结论容易组合，但“平均”不行，比如：</p>
<ol>
<li>算法 1 在最坏的情况下执行 $n$ 次过程 1；</li>
<li>过程 1 在最坏的情况下执行 $m$ 次过程 2；</li>
<li>过程 2 执行若干次基本操作。</li>
</ol>
<p>此时，我们就可以说算法 1 的最坏复杂程度为 $O(n\times m)$。但是如果算法 1 是在平均情况下执行 $n$ 次过程 1，和 $m$ 次过程 2，我们却不能说算法 1 的复杂度是 $\Theta(n\times m)$。因为过程 1 的数据分布我们不清楚。</p>
</li>
</ul>
<h3 id="1-5-3-如何选择-O-f-n-，-Theta-f-n-，-Omega-f-n-？"><a href="#1-5-3-如何选择-O-f-n-，-Theta-f-n-，-Omega-f-n-？" class="headerlink" title="1.5.3 如何选择 $O(f(n))，\Theta(f(n))，\Omega(f(n))$？"></a>1.5.3 如何选择 $O(f(n))，\Theta(f(n))，\Omega(f(n))$？</h3><p>视情况而定。</p>
<ul>
<li>对实时性要求不高的时候，可以考虑平均复杂度。</li>
<li>对实时性要求非常高的情况，就必须考虑最坏的情况了。比如汽车抱死系统，人命关天，时间就是生命。如果用平均复杂度，意味着系统平均反应速度很快，但是偶尔会比较慢。而这个“偶尔”就可能造成无法挽回的损失。</li>
</ul>
<h1 id="Reference"><a href="#Reference" class="headerlink" title="Reference"></a>Reference</h1><ol>
<li><p><a href="https://www.programiz.com/dsa" target="_blank" rel="noopener">DAS Introduction</a></p>
</li>
<li><p><a href="https://zhuanlan.zhihu.com/p/146490404" target="_blank" rel="noopener">算法复杂度分析的那些事</a>, <em>跟小新一起玩编程</em></p>
</li>
<li><p><a href="https://adrianmejia.com/categories/coding/data-structures-and-algorithms-dsa/" target="_blank" rel="noopener">Data Structures and Algorithms (DSA)</a></p>
</li>
<li><p><a href="https://www.zhihu.com/question/28713446/answer/423755676" target="_blank" rel="noopener">算法分析中，为什么分析最坏情况而不是平均情况？</a></p>
</li>
<li><p><a href="https://my.oschina.net/u/240275/blog/232763" target="_blank" rel="noopener">关于&lt;&lt;算法导论&gt;&gt;上的主定理（Master Theorem）的证明</a> </p>
</li>
<li><p><a href="https://blog.csdn.net/caozhk/article/details/24734371?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-4.control&amp;depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-4.control" target="_blank" rel="noopener">主定理的证明及应用举例</a></p>
</li>
</ol>

        </div>
        
          


  <section class='meta' id="footer-meta">
    <hr>
    <div class='new-meta-box'>
      
        
          <div class="new-meta-item date" itemprop="dateUpdated" datetime="2021-09-04T23:19:11+08:00">
  <a class='notlink'>
    <i class="fas fa-clock" aria-hidden="true"></i>
    <p>最后更新于 2021年9月4日</p>
  </a>
</div>

        
      
        
          
  
  <div class="new-meta-item meta-tags"><a class="tag" href="/tags/数据结构/" rel="nofollow"><i class="fas fa-hashtag" aria-hidden="true"></i>&nbsp;<p>数据结构</p></a></div> <div class="new-meta-item meta-tags"><a class="tag" href="/tags/时间复杂度/" rel="nofollow"><i class="fas fa-hashtag" aria-hidden="true"></i>&nbsp;<p>时间复杂度</p></a></div>


        
      
        
          
  <div class="new-meta-item share -mob-share-list">
  <div class="-mob-share-list share-body">
    
      
        <a class="-mob-share-qq" title="QQ好友" rel="external nofollow noopener noreferrer"
          
          href="http://connect.qq.com/widget/shareqq/index.html?url=https://rogerspy.gitee.io/2021/04/22/ds-time-complexity/&title=数据结构与算法：时间复杂度 | Rogerspy's Home&summary=
就像做菜有好吃和不好吃一样，算法也有好的算法和不好的算法。那么我们怎么评价一个算法的好坏呢？
1. 时间复杂度时间复杂度是用来估算算法需要执行的时间的。但是我们并不是直接用时间来估计，而是用一个函数。

时间复杂度不是算法需要执行多久，而是算法需要执行多少步。
"
          
          >
          
            <img src="https://cdn.jsdelivr.net/gh/xaoxuu/assets@19.1.9/logo/128/qq.png">
          
        </a>
      
    
      
        <a class="-mob-share-qzone" title="QQ空间" rel="external nofollow noopener noreferrer"
          
          href="https://sns.qzone.qq.com/cgi-bin/qzshare/cgi_qzshare_onekey?url=https://rogerspy.gitee.io/2021/04/22/ds-time-complexity/&title=数据结构与算法：时间复杂度 | Rogerspy's Home&summary=
就像做菜有好吃和不好吃一样，算法也有好的算法和不好的算法。那么我们怎么评价一个算法的好坏呢？
1. 时间复杂度时间复杂度是用来估算算法需要执行的时间的。但是我们并不是直接用时间来估计，而是用一个函数。

时间复杂度不是算法需要执行多久，而是算法需要执行多少步。
"
          
          >
          
            <img src="https://cdn.jsdelivr.net/gh/xaoxuu/assets@19.1.9/logo/128/qzone.png">
          
        </a>
      
    
      
        <a class='qrcode' rel="external nofollow noopener noreferrer" href=''>
        
          <img src="https://cdn.jsdelivr.net/gh/xaoxuu/assets@19.1.9/logo/128/wechat.png">
        
        </a>
      
    
      
        <a class="-mob-share-weibo" title="微博" rel="external nofollow noopener noreferrer"
          
          href="http://service.weibo.com/share/share.php?url=https://rogerspy.gitee.io/2021/04/22/ds-time-complexity/&title=数据结构与算法：时间复杂度 | Rogerspy's Home&summary=
就像做菜有好吃和不好吃一样，算法也有好的算法和不好的算法。那么我们怎么评价一个算法的好坏呢？
1. 时间复杂度时间复杂度是用来估算算法需要执行的时间的。但是我们并不是直接用时间来估计，而是用一个函数。

时间复杂度不是算法需要执行多久，而是算法需要执行多少步。
"
          
          >
          
            <img src="https://cdn.jsdelivr.net/gh/xaoxuu/assets@19.1.9/logo/128/weibo.png">
          
        </a>
      
    
  </div>
</div>



        
      
    </div>
  </section>


        
        
            <div class="prev-next">
                
                    <section class="prev">
                        <span class="art-item-left">
                            <h6><i class="fas fa-chevron-left" aria-hidden="true"></i>&nbsp;上一页</h6>
                            <h4>
                                <a href="/2021/04/28/24-binary-class-evaluateion-metrics/" rel="prev" title="24种二分类模型的评估方法">
                                  
                                      24种二分类模型的评估方法
                                  
                                </a>
                            </h4>
                            
                                
                                <h6 class="tags">
                                    <a class="tag" href="/tags/评估方法/"><i class="fas fa-hashtag fa-fw" aria-hidden="true"></i>评估方法</a>
                                </h6>
                            
                        </span>
                    </section>
                
                
                    <section class="next">
                        <span class="art-item-right" aria-hidden="true">
                            <h6>下一页&nbsp;<i class="fas fa-chevron-right" aria-hidden="true"></i></h6>
                            <h4>
                                <a href="/2021/04/16/ds-data-structure-introduce/" rel="prev" title="数据结构与算法：数据结构简介">
                                    
                                        数据结构与算法：数据结构简介
                                    
                                </a>
                            </h4>
                            
                                
                                <h6 class="tags">
                                    <a class="tag" href="/tags/数据结构/"><i class="fas fa-hashtag fa-fw" aria-hidden="true"></i>数据结构</a> <a class="tag" href="/tags/queue/"><i class="fas fa-hashtag fa-fw" aria-hidden="true"></i>queue</a>
                                </h6>
                            
                        </span>
                    </section>
                
            </div>
        
      </section>
    </article>
  

  
    <!-- 显示推荐文章和评论 -->



  <article class="post white-box comments">
    <section class="article typo">
      <h4><i class="fas fa-comments fa-fw" aria-hidden="true"></i>&nbsp;评论</h4>
      
      
      
        <section id="comments">
          <div id="gitalk-container"></div>
        </section>
      
      
    </section>
  </article>


  




<!-- 根据页面mathjax变量决定是否加载MathJax数学公式js -->

  <!-- MathJax配置，可通过单美元符号书写行内公式等 -->
<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    "HTML-CSS": {
      preferredFont: "TeX",
      availableFonts: ["STIX","TeX"],
      linebreaks: { automatic:true },
      EqnChunk: (MathJax.Hub.Browser.isMobile ? 10 : 50)
    },
    tex2jax: {
      inlineMath: [ ["$", "$"], ["\\(","\\)"] ],
      processEscapes: true,
      ignoreClass: "tex2jax_ignore|dno",
      skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
    },
    TeX: {
      equationNumbers: { autoNumber: "AMS" },
      noUndefined: { attributes: { mathcolor: "red", mathbackground: "#FFEEEE", mathsize: "90%" } },
      Macros: { href: "{}" }
    },
    messageStyle: "none"
  });
</script>
<!-- 给MathJax元素添加has-jax class -->
<script type="text/x-mathjax-config">
  MathJax.Hub.Queue(function() {
    var all = MathJax.Hub.getAllJax(), i;
    for(i=0; i < all.length; i += 1) {
      all[i].SourceElement().parentNode.className += (all[i].SourceElement().parentNode.className ? ' ' : '') + 'has-jax';
    }
  });
</script>
<!-- 通过连接CDN加载MathJax的js代码 -->
<script type="text/javascript" async
  src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-MML-AM_CHTML">
</script>




  <script>
    window.subData = {
      title: '数据结构与算法：时间复杂度',
      tools: true
    }
  </script>


</div>
<aside class='l_side'>
  
    
    
      
        
          
          
            <section class='widget shake author'>
  <div class='content pure'>
    
      <div class='avatar'>
        <img class='avatar' src='https://cdn.jsdelivr.net/gh/rogerspy/blog-imgs/65-1Z31313530JC.jpeg'/>
      </div>
    
    
    
      <div class="social-wrapper">
        
          
            <a href="/atom.xml"
              class="social fas fa-rss flat-btn"
              target="_blank"
              rel="external nofollow noopener noreferrer">
            </a>
          
        
          
            <a href="mailto:rogerspy@163.com"
              class="social fas fa-envelope flat-btn"
              target="_blank"
              rel="external nofollow noopener noreferrer">
            </a>
          
        
          
            <a href="https://github.com/rogerspy"
              class="social fab fa-github flat-btn"
              target="_blank"
              rel="external nofollow noopener noreferrer">
            </a>
          
        
          
            <a href="https://music.163.com/#/user/home?id=1960721923"
              class="social fas fa-headphones-alt flat-btn"
              target="_blank"
              rel="external nofollow noopener noreferrer">
            </a>
          
        
      </div>
    
  </div>
</section>

          
        
      
        
          
          
            
  <section class='widget toc-wrapper'>
    
<header class='pure'>
  <div><i class="fas fa-list fa-fw" aria-hidden="true"></i>&nbsp;&nbsp;本文目录</div>
  
    <div class='wrapper'><a class="s-toc rightBtn" rel="external nofollow noopener noreferrer" href="javascript:void(0)"><i class="fas fa-thumbtack fa-fw"></i></a></div>
  
</header>

    <div class='content pure'>
      <ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#1-时间复杂度"><span class="toc-text">1. 时间复杂度</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#1-1-计算时间复杂度"><span class="toc-text">1.1 计算时间复杂度</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#1-2-渐进分析"><span class="toc-text">1.2 渐进分析</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-2-1-符号表示"><span class="toc-text">1.2.1 符号表示</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-2-2-渐进分析"><span class="toc-text">1.2.2 渐进分析</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#1-3-非递归算法"><span class="toc-text">1.3 非递归算法</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#1-4-递归算法"><span class="toc-text">1.4 递归算法</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-4-1-迭代法"><span class="toc-text">1.4.1 迭代法</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-4-2-主定理"><span class="toc-text">1.4.2 主定理</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-4-3-主定理证明"><span class="toc-text">1.4.3 主定理证明</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-4-4-主定律应用"><span class="toc-text">1.4.4 主定律应用</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-4-5-主定律的局限性"><span class="toc-text">1.4.5 主定律的局限性</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#1-5-关于时间复杂度的讨论"><span class="toc-text">1.5 关于时间复杂度的讨论</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-5-1-渐进分析有什么缺点？"><span class="toc-text">1.5.1 渐进分析有什么缺点？</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-5-2-为什么通常关心的是-O-f-n-？"><span class="toc-text">1.5.2 为什么通常关心的是 $O(f(n))$？</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-5-3-如何选择-O-f-n-，-Theta-f-n-，-Omega-f-n-？"><span class="toc-text">1.5.3 如何选择 $O(f(n))，\Theta(f(n))，\Omega(f(n))$？</span></a></li></ol></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#Reference"><span class="toc-text">Reference</span></a></li></ol>
    </div>
  </section>


          
        
      
        
          
          
            <section class='widget grid'>
  
<header class='pure'>
  <div><i class="fas fa-map-signs fa-fw" aria-hidden="true"></i>&nbsp;&nbsp;站内导航</div>
  
</header>

  <div class='content pure'>
    <ul class="grid navgation">
      
        <li><a class="flat-box" " href="/"
          
          
          id="home">
          
            <i class="fas fa-clock fa-fw" aria-hidden="true"></i>
          
          近期文章
        </a></li>
      
        <li><a class="flat-box" " href="/blog/"
          
          
          id="blog">
          
            <i class="fas fa-edit fa-fw" aria-hidden="true"></i>
          
          我的博客
        </a></li>
      
        <li><a class="flat-box" " href="/paper_note/"
          
          
          id="paper_note">
          
            <i class="fas fa-book fa-fw" aria-hidden="true"></i>
          
          论文笔记
        </a></li>
      
        <li><a class="flat-box" " href="/algorithm/"
          
          
          id="algorithm">
          
            <i class="fas fa-cube fa-fw" aria-hidden="true"></i>
          
          算法基础
        </a></li>
      
        <li><a class="flat-box" " href="/leetcode/"
          
          
          id="leetcode">
          
            <i class="fas fa-code fa-fw" aria-hidden="true"></i>
          
          Leetcode
        </a></li>
      
        <li><a class="flat-box" " href="/video/"
          
          
          id="video">
          
            <i class="fas fa-film fa-fw" aria-hidden="true"></i>
          
          视频小站
        </a></li>
      
        <li><a class="flat-box" " href="/material/"
          
          
          id="material">
          
            <i class="fas fa-briefcase fa-fw" aria-hidden="true"></i>
          
          学习资料
        </a></li>
      
        <li><a class="flat-box" " href="/dataset/"
          
          
          id="dataset">
          
            <i class="fas fa-database fa-fw" aria-hidden="true"></i>
          
          数据集
        </a></li>
      
        <li><a class="flat-box" " href="/articles/"
          
          
          id="articles">
          
            <i class="fas fa-sticky-note fa-fw" aria-hidden="true"></i>
          
          杂文天地
        </a></li>
      
        <li><a class="flat-box" " href="/blog/archives/"
          
            rel="nofollow"
          
          
          id="blogarchives">
          
            <i class="fas fa-archive fa-fw" aria-hidden="true"></i>
          
          文章归档
        </a></li>
      
        <li><a class="flat-box" " href="/personal_center/"
          
          
          id="personal_center">
          
            <i class="fas fa-university fa-fw" aria-hidden="true"></i>
          
          个人中心
        </a></li>
      
        <li><a class="flat-box" " href="/about/"
          
            rel="nofollow"
          
          
          id="about">
          
            <i class="fas fa-info-circle fa-fw" aria-hidden="true"></i>
          
          关于小站
        </a></li>
      
    </ul>
  </div>
</section>

          
        
      
        
          
          
            <section class='widget list'>
  
<header class='pure'>
  <div><i class="fas fa-terminal fa-fw" aria-hidden="true"></i>&nbsp;&nbsp;机器学习框架</div>
  
</header>

  <div class='content pure'>
    <ul class="entry">
      
        <li><a class="flat-box" title="https://rogerspy.gitee.io/pytorch-zh/" href="https://rogerspy.gitee.io/pytorch-zh/"
          
          
          >
          <div class='name'>
            
              <i class="fas fa-star fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;PyTorch 中文文档
          </div>
          
        </a></li>
      
        <li><a class="flat-box" title="https://keras-zh.readthedocs.io/" href="https://keras-zh.readthedocs.io/"
          
          
          >
          <div class='name'>
            
              <i class="fas fa-star fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;Keras 中文文档
          </div>
          
        </a></li>
      
        <li><a class="flat-box" title="https://tensorflow.google.cn/" href="https://tensorflow.google.cn/"
          
          
          >
          <div class='name'>
            
              <i class="fas fa-star fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;Tensorflow 中文文档
          </div>
          
        </a></li>
      
        <li><a class="flat-box" title="http://scikitlearn.com.cn/" href="http://scikitlearn.com.cn/"
          
          
          >
          <div class='name'>
            
              <i class="fas fa-star fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;Scikit Learn 中文文档
          </div>
          
        </a></li>
      
    </ul>
  </div>
</section>

          
        
      
        
          
          
            <section class='widget list'>
  
<header class='pure'>
  <div><i class="fas fa-wrench fa-fw" aria-hidden="true"></i>&nbsp;&nbsp;百宝箱</div>
  
</header>

  <div class='content pure'>
    <ul class="entry">
      
        <li><a class="flat-box" title="https://rogerspy.github.io/excalidraw-claymate/" href="https://rogerspy.github.io/excalidraw-claymate/"
          
          
            target="_blank"
          
          >
          <div class='name'>
            
              <i class="fas fa-magic fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;Excalidraw-Claymate
          </div>
          
        </a></li>
      
        <li><a class="flat-box" title="https://rogerspy.github.io/jupyterlite/" href="https://rogerspy.github.io/jupyterlite/"
          
          
            target="_blank"
          
          >
          <div class='name'>
            
              <i class="fas fa-terminal fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;JupyterLite
          </div>
          
        </a></li>
      
    </ul>
  </div>
</section>

          
        
      
        
          
          
            <section class='widget list'>
  
<header class='pure'>
  <div><i class="fas fa-eye fa-fw" aria-hidden="true"></i>&nbsp;&nbsp;睁眼看世界</div>
  
</header>

  <div class='content pure'>
    <ul class="entry">
      
        <li><a class="flat-box" title="https://deeplearn.org/" href="https://deeplearn.org/"
          
          
          >
          <div class='name'>
            
              <i class="fas fa-link fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;Deep Learning Monitor
          </div>
          
        </a></li>
      
        <li><a class="flat-box" title="https://paperswithcode.com/sota" href="https://paperswithcode.com/sota"
          
          
          >
          <div class='name'>
            
              <i class="fas fa-link fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;Browse State-of-the-Art
          </div>
          
        </a></li>
      
        <li><a class="flat-box" title="https://huggingface.co/transformers/" href="https://huggingface.co/transformers/"
          
          
          >
          <div class='name'>
            
              <i class="fas fa-link fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;Transformers
          </div>
          
        </a></li>
      
        <li><a class="flat-box" title="https://huggingface.co/models" href="https://huggingface.co/models"
          
          
          >
          <div class='name'>
            
              <i class="fas fa-link fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;Transformers-models
          </div>
          
        </a></li>
      
    </ul>
  </div>
</section>

          
        
      
        
          
          
            
  <section class='widget category'>
    
<header class='pure'>
  <div><i class="fas fa-folder-open fa-fw" aria-hidden="true"></i>&nbsp;&nbsp;文章分类</div>
  
    <a class="rightBtn"
    
      rel="nofollow"
    
    
    href="/categories/"
    title="categories/">
    <i class="fas fa-expand-arrows-alt fa-fw"></i></a>
  
</header>

    <div class='content pure'>
      <ul class="entry">
        
          <li><a class="flat-box" title="/categories/nl2sql/" href="/categories/nl2sql/"><div class='name'>NL2SQL</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/categories/nlp/" href="/categories/nlp/"><div class='name'>NLP</div><div class='badge'>(23)</div></a></li>
        
          <li><a class="flat-box" title="/categories/博客转载/" href="/categories/博客转载/"><div class='name'>博客转载</div><div class='badge'>(5)</div></a></li>
        
          <li><a class="flat-box" title="/categories/数据结构与算法/" href="/categories/数据结构与算法/"><div class='name'>数据结构与算法</div><div class='badge'>(11)</div></a></li>
        
          <li><a class="flat-box" title="/categories/知识图谱/" href="/categories/知识图谱/"><div class='name'>知识图谱</div><div class='badge'>(3)</div></a></li>
        
          <li><a class="flat-box" title="/categories/论文解读/" href="/categories/论文解读/"><div class='name'>论文解读</div><div class='badge'>(2)</div></a></li>
        
          <li><a class="flat-box" title="/categories/语言模型/" href="/categories/语言模型/"><div class='name'>语言模型</div><div class='badge'>(10)</div></a></li>
        
      </ul>
    </div>
  </section>


          
        
      
        
          
          
            
  <section class='widget tagcloud'>
    
<header class='pure'>
  <div><i class="fas fa-fire fa-fw" aria-hidden="true"></i>&nbsp;&nbsp;热门标签</div>
  
    <a class="rightBtn"
    
      rel="nofollow"
    
    
    href="/tags/"
    title="tags/">
    <i class="fas fa-expand-arrows-alt fa-fw"></i></a>
  
</header>

    <div class='content pure'>
      <a href="/tags/attention/" style="font-size: 16.86px; color: #868686">Attention</a> <a href="/tags/cnnlm/" style="font-size: 14px; color: #999">CNNLM</a> <a href="/tags/data-structure/" style="font-size: 14px; color: #999">Data Structure</a> <a href="/tags/deep/" style="font-size: 14px; color: #999">Deep</a> <a href="/tags/ffnnlm/" style="font-size: 14px; color: #999">FFNNLM</a> <a href="/tags/gaussian/" style="font-size: 14px; color: #999">Gaussian</a> <a href="/tags/initialization/" style="font-size: 14px; color: #999">Initialization</a> <a href="/tags/kg/" style="font-size: 16.86px; color: #868686">KG</a> <a href="/tags/lstm/" style="font-size: 14px; color: #999">LSTM</a> <a href="/tags/lstmlm/" style="font-size: 14px; color: #999">LSTMLM</a> <a href="/tags/language-model/" style="font-size: 16.86px; color: #868686">Language Model</a> <a href="/tags/log-linear-language-model/" style="font-size: 14px; color: #999">Log-Linear Language Model</a> <a href="/tags/nlp/" style="font-size: 19.71px; color: #727272">NLP</a> <a href="/tags/nmt/" style="font-size: 22.57px; color: #5f5f5f">NMT</a> <a href="/tags/norm/" style="font-size: 14px; color: #999">Norm</a> <a href="/tags/probabilistic-language-model/" style="font-size: 14px; color: #999">Probabilistic Language Model</a> <a href="/tags/rnnlm/" style="font-size: 14px; color: #999">RNNLM</a> <a href="/tags/roc-auc/" style="font-size: 14px; color: #999">ROC-AUC</a> <a href="/tags/transformer/" style="font-size: 24px; color: #555">Transformer</a> <a href="/tags/context2vec/" style="font-size: 14px; color: #999">context2vec</a> <a href="/tags/divide-conquer/" style="font-size: 14px; color: #999">divide-conquer</a> <a href="/tags/insertion/" style="font-size: 16.86px; color: #868686">insertion</a> <a href="/tags/insertion-deletion/" style="font-size: 15.43px; color: #8f8f8f">insertion-deletion</a> <a href="/tags/knowledge-modelling/" style="font-size: 15.43px; color: #8f8f8f">knowledge-modelling</a> <a href="/tags/nl2infographic/" style="font-size: 14px; color: #999">nl2infographic</a> <a href="/tags/nl2sql/" style="font-size: 14px; color: #999">nl2sql</a> <a href="/tags/ontology/" style="font-size: 14px; color: #999">ontology</a> <a href="/tags/parallel-recurrent/" style="font-size: 14px; color: #999">parallel-recurrent</a> <a href="/tags/pytorch/" style="font-size: 14px; color: #999">pytorch</a> <a href="/tags/queue/" style="font-size: 18.29px; color: #7c7c7c">queue</a> <a href="/tags/sparse/" style="font-size: 14px; color: #999">sparse</a> <a href="/tags/stack/" style="font-size: 14px; color: #999">stack</a> <a href="/tags/tensorflow/" style="font-size: 14px; color: #999">tensorflow</a> <a href="/tags/text2viz/" style="font-size: 14px; color: #999">text2viz</a> <a href="/tags/weighted-head/" style="font-size: 14px; color: #999">weighted-head</a> <a href="/tags/半监督语言模型/" style="font-size: 14px; color: #999">半监督语言模型</a> <a href="/tags/双数组前缀树/" style="font-size: 14px; color: #999">双数组前缀树</a> <a href="/tags/推荐系统/" style="font-size: 14px; color: #999">推荐系统</a> <a href="/tags/数据结构/" style="font-size: 21.14px; color: #686868">数据结构</a> <a href="/tags/数组/" style="font-size: 14px; color: #999">数组</a> <a href="/tags/时间复杂度/" style="font-size: 14px; color: #999">时间复杂度</a> <a href="/tags/算法/" style="font-size: 14px; color: #999">算法</a> <a href="/tags/评估方法/" style="font-size: 14px; color: #999">评估方法</a> <a href="/tags/词向量/" style="font-size: 14px; color: #999">词向量</a> <a href="/tags/隐式正则化/" style="font-size: 14px; color: #999">隐式正则化</a>
    </div>
  </section>


          
        
      
        
          
          
            


  <section class='widget music'>
    
<header class='pure'>
  <div><i class="fas fa-compact-disc fa-fw" aria-hidden="true"></i>&nbsp;&nbsp;最近在听</div>
  
    <a class="rightBtn"
    
      rel="external nofollow noopener noreferrer"
    
    
      target="_blank"
    
    href="https://music.163.com/#/user/home?id=1960721923"
    title="https://music.163.com/#/user/home?id=1960721923">
    <i class="far fa-heart fa-fw"></i></a>
  
</header>

    <div class='content pure'>
      
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/aplayer@1.7.0/dist/APlayer.min.css">
  <div class="aplayer"
    data-theme="#1BCDFC"
    
    
    data-mode="circulation"
    data-server="netease"
    data-type="playlist"
    data-id="2957571193"
    data-volume="0.7">
  </div>
  <script src="https://cdn.jsdelivr.net/npm/aplayer@1.7.0/dist/APlayer.min.js"></script>
  <script src="https://cdn.jsdelivr.net/npm/meting@1.1.0/dist/Meting.min.js"></script>


    </div>
  </section>


          
        
      
    

  
</aside>

<footer id="footer" class="clearfix">
  <div id="sitetime"></div>
  
  
    <div class="social-wrapper">
      
        
          <a href="/atom.xml"
            class="social fas fa-rss flat-btn"
            target="_blank"
            rel="external nofollow noopener noreferrer">
          </a>
        
      
        
          <a href="mailto:rogerspy@163.com"
            class="social fas fa-envelope flat-btn"
            target="_blank"
            rel="external nofollow noopener noreferrer">
          </a>
        
      
        
          <a href="https://github.com/rogerspy"
            class="social fab fa-github flat-btn"
            target="_blank"
            rel="external nofollow noopener noreferrer">
          </a>
        
      
        
          <a href="https://music.163.com/#/user/home?id=1960721923"
            class="social fas fa-headphones-alt flat-btn"
            target="_blank"
            rel="external nofollow noopener noreferrer">
          </a>
        
      
    </div>
  
  <br>
  <div><p>博客内容遵循 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议</a></p>
</div>
  <div>
    本站使用
    <a href="https://xaoxuu.com/wiki/material-x/" target="_blank" class="codename">Material X</a>
    作为主题
    
      ，
      总访问量为
      <span id="busuanzi_value_site_pv"><i class="fas fa-spinner fa-spin fa-fw" aria-hidden="true"></i></span>
      次
    
    。
  </div>
	</footer>

<script>setLoadingBarProgress(80);</script>
<!-- 点击特效，输入特效 运行时间 -->
<script type="text/javascript" src="/cool/cooltext.js"></script>
<script type="text/javascript" src="/cool/clicklove.js"></script>
<script type="text/javascript" src="/cool/sitetime.js"></script>



      <script>setLoadingBarProgress(60);</script>
    </div>
    <a class="s-top fas fa-arrow-up fa-fw" href='javascript:void(0)'></a>
  </div>
  <script src="https://cdn.jsdelivr.net/npm/jquery@3.3.1/dist/jquery.min.js"></script>

  <script>
    var GOOGLE_CUSTOM_SEARCH_API_KEY = "";
    var GOOGLE_CUSTOM_SEARCH_ENGINE_ID = "";
    var ALGOLIA_API_KEY = "";
    var ALGOLIA_APP_ID = "";
    var ALGOLIA_INDEX_NAME = "";
    var AZURE_SERVICE_NAME = "";
    var AZURE_INDEX_NAME = "";
    var AZURE_QUERY_KEY = "";
    var BAIDU_API_ID = "";
    var SEARCH_SERVICE = "hexo" || "hexo";
    var ROOT = "/"||"/";
    if(!ROOT.endsWith('/'))ROOT += '/';
  </script>

<script src="//instant.page/1.2.2" type="module" integrity="sha384-2xV8M5griQmzyiY3CDqh1dn4z3llDVqZDqzjzcY+jCBCk/a5fXJmuZ/40JJAPeoU"></script>


  <script async src="https://cdn.jsdelivr.net/npm/scrollreveal@4.0.5/dist/scrollreveal.min.js"></script>
  <script type="text/javascript">
    $(function() {
      const $reveal = $('.reveal');
      if ($reveal.length === 0) return;
      const sr = ScrollReveal({ distance: 0 });
      sr.reveal('.reveal');
    });
  </script>


  <script src="https://cdn.jsdelivr.net/npm/node-waves@0.7.6/dist/waves.min.js"></script>
  <script type="text/javascript">
    $(function() {
      Waves.attach('.flat-btn', ['waves-button']);
      Waves.attach('.float-btn', ['waves-button', 'waves-float']);
      Waves.attach('.float-btn-light', ['waves-button', 'waves-float', 'waves-light']);
      Waves.attach('.flat-box', ['waves-block']);
      Waves.attach('.float-box', ['waves-block', 'waves-float']);
      Waves.attach('.waves-image');
      Waves.init();
    });
  </script>


  <script async src="https://cdn.jsdelivr.net/gh/xaoxuu/cdn-busuanzi@2.3/js/busuanzi.pure.mini.js"></script>




  
  
  
    <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery-backstretch/2.0.4/jquery.backstretch.min.js"></script>
    <script type="text/javascript">
      $(function(){
        if ('.cover') {
          $('.cover').backstretch(
          ["https://cdn.jsdelivr.net/gh/rogerspy/blog-imgs/a0c9e6f9efad8b731cb7376504bd10d79d2053.jpg"],
          {
            duration: "6000",
            fade: "2500"
          });
        } else {
          $.backstretch(
          ["https://cdn.jsdelivr.net/gh/rogerspy/blog-imgs/a0c9e6f9efad8b731cb7376504bd10d79d2053.jpg"],
          {
            duration: "6000",
            fade: "2500"
          });
        }
      });
    </script>
  







  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.css">
  <script src="https://cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.min.js"></script>
  <script type="text/javascript">
    var gitalk = new Gitalk({
      clientID: "35a5e4dc744cc7d162af",
      clientSecret: "7b5a409e17ce0c1971f284eac9f8902eb4b8feba",
      repo: "rogerspy.github.io",
      owner: "Rogerspy",
      admin: "Rogerspy",
      
        id: "/wiki/material-x/",
      
      distractionFreeMode: false  // Facebook-like distraction free mode
    });
    gitalk.render('gitalk-container');
  </script>





  <script src="https://cdn.jsdelivr.net/gh/xaoxuu/cdn-material-x@19.5/js/app.js"></script>


  <script src="https://cdn.jsdelivr.net/gh/xaoxuu/cdn-material-x@19.5/js/search.js"></script>




<!-- 复制 -->
<script src="https://cdn.jsdelivr.net/npm/clipboard@2/dist/clipboard.min.js"></script>
<script>
  let COPY_SUCCESS = "复制成功";
  let COPY_FAILURE = "复制失败";
  /*页面载入完成后，创建复制按钮*/
  !function (e, t, a) {
    /* code */
    var initCopyCode = function(){
      var copyHtml = '';
      copyHtml += '<button class="btn-copy" data-clipboard-snippet="">';
      copyHtml += '  <i class="fa fa-copy"></i><span>复制</span>';
      copyHtml += '</button>';
      $(".highlight .code pre").before(copyHtml);
      var clipboard = new ClipboardJS('.btn-copy', {
        target: function(trigger) {
          return trigger.nextElementSibling;
        }
      });

      clipboard.on('success', function(e) {
        //您可以加入成功提示
        console.info('Action:', e.action);
        console.info('Text:', e.text);
        console.info('Trigger:', e.trigger);
        success_prompt(COPY_SUCCESS);
        e.clearSelection();
      });
      clipboard.on('error', function(e) {
        //您可以加入失败提示
        console.error('Action:', e.action);
        console.error('Trigger:', e.trigger);
        fail_prompt(COPY_FAILURE);
      });
    }
    initCopyCode();

  }(window, document);

  /**
   * 弹出式提示框，默认1.5秒自动消失
   * @param message 提示信息
   * @param style 提示样式，有alert-success、alert-danger、alert-warning、alert-info
   * @param time 消失时间
   */
  var prompt = function (message, style, time)
  {
      style = (style === undefined) ? 'alert-success' : style;
      time = (time === undefined) ? 1500 : time*1000;
      $('<div>')
          .appendTo('body')
          .addClass('alert ' + style)
          .html(message)
          .show()
          .delay(time)
          .fadeOut();
  };

  // 成功提示
  var success_prompt = function(message, time)
  {
      prompt(message, 'alert-success', time);
  };

  // 失败提示
  var fail_prompt = function(message, time)
  {
      prompt(message, 'alert-danger', time);
  };

  // 提醒
  var warning_prompt = function(message, time)
  {
      prompt(message, 'alert-warning', time);
  };

  // 信息提示
  var info_prompt = function(message, time)
  {
      prompt(message, 'alert-info', time);
  };

</script>


<!-- fancybox -->
<script src="https://cdn.jsdelivr.net/gh/fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.js"></script>
<script>
  let LAZY_LOAD_IMAGE = "";
  $(".article-entry").find("fancybox").find("img").each(function () {
      var element = document.createElement("a");
      $(element).attr("data-fancybox", "gallery");
      $(element).attr("href", $(this).attr("src"));
      /* 图片采用懒加载处理时,
       * 一般图片标签内会有个属性名来存放图片的真实地址，比如 data-original,
       * 那么此处将原本的属性名src替换为对应属性名data-original,
       * 修改如下
       */
       if (LAZY_LOAD_IMAGE) {
         $(element).attr("href", $(this).attr("data-original"));
       }
      $(this).wrap(element);
  });
</script>





  <script>setLoadingBarProgress(100);</script>
</body>
</html>
